package com.mystudy.leetcode.problem.link.p_203;

import com.mystudy.leetcode.base.ListNode;

/**
 * @author 周志龙
 * @Email 15216876513@163.com
 * @Date on 2019/7/1 23:40
 * @Description 移除链表元素
 */
public class Solution {
    /**
     * 不使用虚拟头结点，需要对头结点做特殊处理
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }

        if(head == null){
            return null;
        }

        ListNode prev = head;
        while(prev.next != null){
            if(prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else{
                prev = prev.next;
            }
        }
        return head;
    }

    /**
     * 使用虚拟头结点，更加简单
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements2(ListNode head,int val){
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        while(prev.next != null){
            if(prev.next.val == val){
                prev.next = prev.next.next;
            }else{
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }

    /**
     * 用递归的方式
     * 最小问题的解为：当当前head的val==val，那么返回子任务的结果。
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElement3(ListNode head,int val){
        if(head == null){
            return null;
        }
        ListNode result = removeElement3(head.next, val);
        if(head.val == val){
            return result;
        }else{
            head.next = result;
            return head;
        }
    }


}
